//https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/?envType=study-plan-v2&envId=top-100-liked
//方法1:堆排序,能写出堆排序，基本就解决了，堆排序每次也是只排好一个数字，速度好于快速排序；
//方法2:最小堆实现,实现相对比较巧妙；
//方法3:快速排序实现思路；

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution1 {
public:
    int findKthLargest(vector<int>& arr, int k) {
        if (k>arr.size() ||k<1) return -1;

        if(arr.size()<2) return arr[0];
        for(int i = arr.size()-1;i>=0;i--){
            heapify(arr,i,arr.size());
        }

        int heapSize = arr.size();
        std::swap(arr[0],arr[--heapSize]);
        int ask=k;
        ask--;
        while(heapSize>0&& ask>0){
            heapify(arr,0,heapSize);
            std::swap(arr[0],arr[--heapSize]);
        }

        return arr[arr.size()-k];
    }
    // 堆排序-solution2
    void heapify(std::vector<int>& arr,int index,int heapSize){
        int left = index*2 +1;
        while(left<heapSize){
            int largest = left+1 < heapSize && arr[left+1]>arr[left]?
                left+1 :left;
            largest = arr[largest] > arr[index]?largest:index;
            if(largest == index){
                break;
            }
            std::swap(arr[largest],arr[index]);
            index = largest;
            left = index*2 +1;
        }
    }
};


class Solution2 {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if (k>nums.size() ||k<1) return -1;
        // 最小堆， 存储右边一半的数据，堆顶为最小值
        priority_queue<int, vector<int>, greater<int>> minHeap;
        for(size_t i=0;i<k;++i){
            minHeap.push(nums[i]);
        }
        for(size_t i=k;i<nums.size();++i){
            int min_top=minHeap.top();
            if(min_top<nums[i]){
                minHeap.pop();
                minHeap.push(nums[i]);
            }
        }
        return minHeap.top();
    }
};


class Solution3 {
public:
    int findKthLargest(vector<int>& input, int k) {

        if (input.size() < k || k < 1) {
            return -1;
        }
        int start = 0;
        int end = input.size()-1;
        std::vector<int> index_vec = partition(input,start,end);
        while(index_vec[0]!=input.size()-k){
            if(index_vec[0] > input.size()-k){
                end = index_vec[0] -1;
                index_vec = partition(input,start,end);
            }
            else if (index_vec[0] < input.size()-k) {
                start = index_vec[0] +1;
                index_vec = partition(input,start,end);
            }
        }
        return input[input.size()-k];
    }


    std::vector<int> partition(vector<int>& numbers, int l, int r) {
        int rand_num = (rand()%(r-l+1) + l);
        std::swap(numbers[rand_num],numbers[r]);

        int less = l - 1;
        int more = r;
        while (l < more) {
            if (numbers[l] < numbers[r]) {
                std::swap(numbers[++less], numbers[l++]);
            } else if (numbers[l] > numbers[r]) {
                std::swap(numbers[l], numbers[--more]);
            } else {
                ++l;
            }
        }
        std::swap(numbers[more], numbers[r]);
        return std::vector<int> {++less, more};
    };
};